package com.lw.leetcode.arr.c;

/**
 * Created with IntelliJ IDEA.
 * 76. 最小覆盖子串
 * 剑指 Offer II 017. 含有所有字符的最短字符串
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/10 9:12
 */
public class MinWindow {


    public static void main(String[] args) {
        MinWindow test = new MinWindow();

        // 输入：s = "ADOBECODEBANC", t = "ABC"
        //输出："BANC"
        //示例 2：
        //
        //输入：s = "a", t = "a"
        //输出："a"
        //示例 3:
        //
        //输入: s = "a", t = "aa"
        //输出: ""
        //
        //来源：力扣（LeetCode）
        //链接：https://leetcode-cn.com/problems/minimum-window-substring
        //著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

        String s = "ADOBECODEBANC";
        String t = "ABC";
        String s1 = test.minWindow(s, t);
        System.out.println(s1);
    }

    public String minWindow(String s, String t) {
        int tl = t.length();
        int sl = s.length();
        if (sl < tl) {
            return "";
        }
        int[] arr = new int[58];
        for (int i = 0; i < tl; i++) {
            arr[t.charAt(i) - 'A']++;
        }

        int[] items = new int[58];
        for (int i = 0; i < tl; i++) {
            items[s.charAt(i) - 'A']++;
        }
        if (find(arr, items)) {
            return s.substring(0, tl);
        }
        int st = 0;
        int end = tl;

        int min = Integer.MAX_VALUE;
        int st1 = 0;
        int end1 = 0;

        while (end < sl) {
            items[s.charAt(end++) - 'A']++;
            if (find(arr, items)) {
                if (end - st < min) {
                    min = end - st;
                    st1 = st;
                    end1 = end ;
                }
                while (true) {
                    items[s.charAt(st++) - 'A']--;
                    if (!find(arr, items)) {

                        if (end - st + 1 < min) {
                            min = end - st + 1;
                            st1 = st - 1;
                            end1 = end;
                        }

                        min = Math.min(min, end - st + 1);
                        break;
                    }
                }
            }

        }

        return s.substring(st1, end1);


    }

    private boolean find (int[] arr, int[] items) {
        for (int i = 0; i < 58; i++) {
            if (arr[i] > items[i]) {
                return false;
            }
        }
        return true;
    }

}
